package junior.回溯法;

import javax.swing.*;
import java.awt.event.ActionListener;

/**
 * 解决9皇后问题，用时:9毫秒，计算结果:352
 * 解决10皇后间题，用时:9毫秒，计算结果:724
 * 解决11皇后问题，用时:21毫秒，计算结果:2680
 * 解决12皇后问题，用时:32毫秒，计算结果:14200
 * 解决13皇后问题，用时:166毫秒，计算结果:73712
 * 解决14皇后问题，用时:750毫秒，计算结果:365596
 * 解决15皇后间题，用时:4903毫秒，计算结果:2279184
 * 解决16皇后问题，用时:33265毫秒，计算结果:14772512
 * 解决17皇后问题，用时:267460毫秒，计算结果:95815104
 * N后问题，1-N的排列，行列都不需要考虑，仅考虑斜线
 */
public class n后问题 {
    static int[] stack = new int[10000]; // 状态位
    static int[] check = new int[10000]; // 0: 未使用，1：使用
    static int top = 0;
    static int total = 0;
    static int N = 5;  // 16皇后 87秒  【14:1992ms  365596个】
    public static void main(String[] args){
        new Thread(()->{
            for (int i = 0; i < 50; i++) {
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("i = " + i + " s");
            }
        }).start();
        long l2 = System.currentTimeMillis();
            fun3(0);
        long l3 = System.currentTimeMillis();
        System.out.println(l3-l2 + "\tms");
        System.out.println("total: "+total);

    }

    /**
     * n=3个元素里面取 n=3 个，进行排列（元素，可以重复，且有顺序排列）
     * @param n
     */
    // 传统方法
    public static void fun1(int n){// 15皇后 ≈ 太久
        if(n == N){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
            boolean isOk = true;
            // queenPos[j] == i || abs(queenPos[j]-i) == abs(k-j)   行距离       列距离  ( 相等即为在对角线上 )
            for (int i = 0; i < top; i++) {
                for (int j = i+1; j < top; j++) {
                    if(Math.abs(j-i) == Math.abs(stack[j]- stack[i] )){
                        isOk = false;
                        break;
                    }
                }
                if(isOk == false){
                    break;
                }
            }
            if(isOk == true){
//                for (int i = 0; i < N; i++) {
//                    System.out.print(stack[i]+" ");
//                }
//                System.out.println();
                total++;
                System.out.println("total = " + total);
            }
            return;
        }
        for (int i = 1; i <= N; i++) {  // n 个元素
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                check[i] = 1;
                stack[top++] = i;
                fun1(n+1);
                top--;
                check[i] = 0;
            }
        }
    }
    // 三角形判断法
    public static void fun2(int n){ // 15皇后 ≈ 15000ms = 15s  （15620、15644、15261）
        if(n == N){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
//            for (int i = 0; i < N; i++) {
//                System.out.print(stack[i]+" ");
//            }
//            System.out.println();
            total++;
            return;
        }
        for (int i = 1; i <= N; i++) {  // n 个元素
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                boolean i_isOk = true;
                if(n > 0){
                    for (int j = 0; j < n; j++) {
                        if(Math.abs(n-j) == Math.abs(i- stack[j])){  // 列差：低    行差：高
                            i_isOk = false;
                            break;
                        }
                    }
                }
                if(i_isOk){
                    check[i] = 1;
                    stack[top++] = i;
                    fun2(n+1);
                    top--;
                    check[i] = 0;
                }
            }
        }
    }
    // 行列的加减，二维表格斜线规律判断法
    public static void fun3(int n){ // 15皇后 ≈ 12000ms = 12s （12327、
        if(n == N){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
            for (int i = 0; i < n; i++) {
                System.out.print(stack[i]+" ");
            }
            System.out.println();
            total++;
            return;
        }
        for (int i = 1; i <= N; i++) {  // n 个元素
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                boolean i_isOk = true;
                if(n > 0){
                    for (int j = 0; j < n; j++) {
                        if(((n+i) == (j+stack[j]) || (n-i) == (j-stack[j]))){  // 列差：低    行差：高
                            i_isOk = false;
                            break;
                        }
                    }
                }
                if(i_isOk){
                    check[i] = 1;
                    stack[top++] = i;
                    fun3(n+1);
                    top--;
                    check[i] = 0;
                }
            }
        }
    }
    // 应用函数，y = - |x - i | + j;
    public static void fun4(int n){ // 15皇后 ≈ 13000ms = 13s （13378、
        if(n == N){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
//            for (int i = 0; i < N; i++) {
//                System.out.print(stack[i]+" ");
//            }
//            System.out.println();
            total++;
            return;
        }
            // n：当前行数，i：当前列数
            // i：遍历行数，stack[i]：遍历列数
        for (int i = 1; i <= N; i++) {  // n 个元素
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                boolean i_isOk = true;
                for (int j = 0; j < n; j++) {
                    if(n>0){
                        if(n - Math.abs(stack[j] -i) == j){
                            i_isOk = false;
                            break;
                        }
                    }
                }
                if(i_isOk){
                    check[i] = 1;
                    stack[top++] = i;
                    fun4(n+1);
                    top--;
                    check[i] = 0;
                }
            }
        }
    }
    // 对称剪枝
    public static void fun5(int n){ // 15皇后 ≈ 12000ms = 12s （12327、
        if(n == N){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
            total++;
            return;
        }

        for (int i = 1; i <= N; i++) {  // n行下，第i列的
            if(n == 0){ // 第一行
                if(i == N/2+1)
                    total *= 2;
                if(i > (N+1)/2)
                    return;
            }
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                boolean i_isOk = true;
                if(n > 0){
                    for (int j = 0; j < n; j++) {
                        if(((n+i) == (j+stack[j]) || (n-i) == (j-stack[j]))){  // 列差：低    行差：高
                            check[i] = 1;
                            stack[top++] = i;
                            fun3(n+1);
                            top--;
                            check[i] = 0;
                        }
                    }
                }
                if(i_isOk){
                    check[i] = 1;
                    stack[top++] = i;
                    fun3(n+1);
                    top--;
                    check[i] = 0;
                }
            }
        }
    }

}
